package leetcode.D100.T33;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-10 23:21:48 星期二
 */

public class Solution {
    // 一刷
    /*public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target || nums[left] == target || nums[right] == target) {
                return nums[mid] == target ? mid : (nums[left] == target ? left : right);
            }
            if(nums[left] < nums[right]) {
                if(target < nums[left] || target > nums[right]) {
                    return -1;
                } else if(nums[mid] < target){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if(target > nums[left]) {
                    if(nums[mid] < nums[right] || nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else if (target < nums[right]) {
                    if(nums[mid] > nums[left] || nums[mid] < target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else {
                    return -1;
                }
            }
        }
        return nums[0] == target ? 0 : -1;
    }*/

    // 二刷
    /*public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left <= right) {
            if (nums[left] == target)
                return left;
            if (nums[right] == target)
                return right;
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[left] < nums[right]) {
                if (nums[mid] < target)
                    left = mid + 1;
                else
                    right = mid - 1;
            } else {
                if (target < nums[right]) {
                    if (nums[mid] < target || nums[mid] > nums[left])
                        left = mid + 1;
                    else {
                        left++;
                        right = mid - 1;
                    }
                } else if (target > nums[left]) {
                    if (nums[mid] > target || nums[mid] < nums[right])
                        right = mid - 1;
                    else {
                        right--;
                        left = mid + 1;
                    }
                } else
                    return -1;
            }
        }
        return -1;
    }*/

    // 三刷
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left < right) {
            if (nums[left] == target)
                return left;
            if (nums[right] == target)
                return right;
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[left] < nums[right]) {
                if (nums[mid] > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (target > nums[right] && target < nums[left])
                    return -1;
                else if (target < nums[right]) {
                    if (nums[mid] > nums[right] || nums[mid] < target)
                        left = mid + 1;
                    else {
                        right = mid - 1;
                        left++;
                    }
                } else {
                    if (nums[mid] < nums[left] || nums[mid] > target)
                        right = mid - 1;
                    else {
                        left = mid + 1;
                        right--;
                    }
                }
            }
        }
        return nums[left] == target ? left : -1;
    }
}
